#include "StdAfx.h"
#include "BinTree.h"



BinTree::BinTree(void)
{
}


BinTree::~BinTree(void)
{
}

void BinTree::PreInOrderBuild(int preOrder[],int inOrder[],int preLength,int inLength){
	if(preOrder == NULL || inOrder == NULL){
		return;
	}
	BinTreeNode* root = NULL;
	root = PreInBuildRecursion(preOrder,inOrder,0,preLength-1,0,inLength-1);

	PreOrderRecursion(root);
}

BinTreeNode* BinTree::PreInBuildRecursion(int* preOrder,int* inOrder,int preBegin,int preEnd,int inBegin,int inEnd){
	if(preBegin>preEnd || inBegin>inEnd){
		return NULL;
	}

	BinTreeNode* root = new BinTreeNode();
	root->data = preOrder[preBegin];

	int inPoi = inBegin;
	while(inPoi<=inEnd){
		if(preOrder[preBegin] == inOrder[inPoi]){
			break;
		}
		inPoi++;
	}
	cout<<"inPoi="<<inPoi<<"  preBegin="<<preBegin<<"  preEnd="<<preEnd<<"  inBegin="<<inBegin<<"  inEnd="<<inEnd<<endl;
	BinTreeNode* leftChild = PreInBuildRecursion(preOrder,inOrder,preBegin+1,preBegin+inPoi-inBegin,inBegin,inPoi-1);
	BinTreeNode* rightChild = PreInBuildRecursion(preOrder,inOrder,preBegin+inPoi-inBegin+1,preEnd,inPoi+1,inEnd);

	root->left = leftChild;
	root->right = rightChild;

	return root;
}

void BinTree::VerifyChild(BinTreeNode* bigTree,BinTreeNode* smallTree){
	if(bigTree == NULL || smallTree == NULL){
		return;
	}
	cout<<"begin"<<endl;
	bool result = PreOrderVerify(bigTree,smallTree);
	cout<<result<<endl;
}

bool BinTree::PreOrderVerify(BinTreeNode* bigTree,BinTreeNode* smallTree){
	if(bigTree == NULL || smallTree == NULL){
		return false;
	}
	bool result = false;

	if(bigTree->data == smallTree->data){
		result = DoesHaveChild(bigTree,smallTree);
	}
	if(!result ){
		result = PreOrderVerify(bigTree->left,smallTree);
	}
	if(!result){
		result = PreOrderVerify(bigTree->right,smallTree);
	}
	cout<<"preOrderVerfity = "<<result<<endl;
	return result;
}

bool BinTree::DoesHaveChild(BinTreeNode* bigTree,BinTreeNode* smallTree){
	if(smallTree == NULL){
		return true;
	}
	if(bigTree == NULL){
		return false;
	}

	if(bigTree->data != smallTree->data){
		return false;
	}

	return DoesHaveChild(bigTree->left,smallTree->left)&&DoesHaveChild(bigTree->right,smallTree->right);

}

void BinTree::IteratorTree(BinTreeNode* root){
	if(root == NULL){
		return;
	}
	PreOrderRecursion(root);
	cout<<endl;
	InOrderRecursion(root);
	cout<<endl;
	PostOrderRecursion(root);
	cout<<endl;
	PreOrderStack(root);
	cout<<endl;
	InOrderStack(root);
	cout<<endl;
	PostOrderStack(root);
	cout<<endl;
}

void BinTree::PreOrderRecursion(BinTreeNode* root){
	if(root == NULL){
		return;
	}
	cout<<root->data;
	PreOrderRecursion(root->left);
	PreOrderRecursion(root->right);
}

void BinTree::InOrderRecursion(BinTreeNode* root){
	if(root == NULL){
		return;
	}
	
	InOrderRecursion(root->left);
	cout<<root->data;
	InOrderRecursion(root->right);
}

void BinTree::PostOrderRecursion(BinTreeNode* root){
	if(root == NULL){
		return;
	}
	PostOrderRecursion(root->left);
	PostOrderRecursion(root->right);
	cout<<root->data;
}

void BinTree::PreOrderStack(BinTreeNode* root){
	if(root == NULL){
		return;
	}
	stack<BinTreeNode*> preStack;
	preStack.push(root);
	
	while(!preStack.empty()){
		
		while(preStack.top() != NULL){
			cout<<preStack.top()->data;
			preStack.push(preStack.top()->left);
		}
		preStack.pop();

		if(!preStack.empty()){
			BinTreeNode * pTemp = preStack.top();
			preStack.pop();
			preStack.push(pTemp->right);
		}
		
	}
}

void BinTree::InOrderStack(BinTreeNode* root){
	if(root == NULL){
		return;
	}
	stack<BinTreeNode*> preStack;
	preStack.push(root);
	
	while(!preStack.empty()){
		
		while(preStack.top() != NULL){
			preStack.push(preStack.top()->left);
		}
		preStack.pop();

		if(!preStack.empty()){
			BinTreeNode * pTemp = preStack.top();
			cout<<pTemp->data;
			preStack.pop();
			preStack.push(pTemp->right);
		}
		
	}
}

void BinTree::PostOrderStack(BinTreeNode* root){
	if(root == NULL){
		return;
	}
	stack<BinTreeNode*> postStack;
	postStack.push(root);
	BinTreeNode* preVisit = NULL;
	BinTreeNode* curVisit = NULL;

	while(!postStack.empty()){
		
		curVisit = postStack.top();

		if((curVisit->left == NULL && curVisit->right == NULL)
			|| (preVisit != NULL && (preVisit == curVisit->left || preVisit == curVisit->right))){
				cout<<curVisit->data;
				postStack.pop();
				preVisit = curVisit;
		}else{
			if(curVisit->right != NULL){
				postStack.push(curVisit->right);
			}
			if(curVisit->left != NULL){
				postStack.push(curVisit->left);
			}
		}

	}
}

void BinTree::TreeHeight(BinTreeNode* root){
	if(root == NULL){
		return;
	}
	int height = TreeHeightRecursion(root);
	cout<<height<<endl;
	bool isBalanced = IsBalancedTree(root);
	cout<<isBalanced<<endl;
}

int BinTree::TreeHeightRecursion(BinTreeNode* root){
	if(root == NULL){
		return 0;
	}

	int leftHeight = TreeHeightRecursion(root->left);
	int rightHeight = TreeHeightRecursion(root->right);

	if(leftHeight > rightHeight){
		return leftHeight+1;
	}

	return rightHeight+1;
}

bool BinTree::IsBalancedTree(BinTreeNode* root){
	if(root == NULL){
		return true;
	}

	bool isBalanced = true;

	if(isBalanced){
		int leftChildHeight = TreeHeightRecursion(root->left);
		int rightChildHeight = TreeHeightRecursion(root->right);

		if((leftChildHeight - rightChildHeight >1) || (leftChildHeight - rightChildHeight <-1)){
			isBalanced = false;
		}else{
			isBalanced = IsBalancedTree(root->left) && IsBalancedTree(root->right);
		}
	}

	return isBalanced;
}

void BinTree::MirrorBinTree(BinTreeNode* root){
	if(root == NULL){
		return;
	}
	MirrorTreeRecursion(root);
	PreOrderRecursion(root);
}

void BinTree::MirrorTreeRecursion(BinTreeNode* root){
	if(root == NULL){
		return;
	}
	BinTreeNode* tempNode;
	tempNode = root->left;
	root->left = root->right;
	root->right = tempNode;

	MirrorTreeRecursion(root->left);
	MirrorTreeRecursion(root->right);
}

void BinTree::OrderTreePostConstruct(int* orderPostTree,int length){
	if(orderPostTree == NULL){
		return;
	}
	BinTreeNode* root = OrderTreePostRecursion(orderPostTree,0,length-1);
	PreOrderRecursion(root);
}

BinTreeNode* BinTree::OrderTreePostRecursion(int* orderPostTree,int beginIndex,int endIndex){

	if(beginIndex>endIndex){
		return NULL;
	}

	BinTreeNode* root = new BinTreeNode();
	root->data = orderPostTree[endIndex];

	int smallIndex = 0;
	while(smallIndex<=endIndex){
		if(orderPostTree[smallIndex]<orderPostTree[endIndex]){
			smallIndex++;
		}else{
			break;
		}
	}
	BinTreeNode* rightChild =  OrderTreePostRecursion(orderPostTree,smallIndex,endIndex-1);
	BinTreeNode* leftChild = OrderTreePostRecursion(orderPostTree,beginIndex,smallIndex-1);

	root->left = leftChild;
	root->right = rightChild;

	return root;
}

void BinTree::PrintTreePath(BinTreeNode* root,int sum){
	if(root == NULL){
		return;
	}

	vector<BinTreeNode*> nodeVector;
	int currSum = 0;
	PrintTreeSumPath(root,nodeVector,sum,currSum);
}
void BinTree::PrintTreeSumPath(BinTreeNode* root,vector<BinTreeNode*> nodeVector,int sum,int currentSum){
	if(root == NULL){
		return;
	}
	
	currentSum += root->data;
	nodeVector.push_back(root);
	//cout<<"*currentSum= "<<currentSum<<";sum="<<sum<<endl;
	if(currentSum == sum){
		
		PrintVector(nodeVector);
		return;
	}
	
	PrintTreeSumPath(root->left,nodeVector,sum,currentSum);
	PrintTreeSumPath(root->right,nodeVector,sum,currentSum);

	nodeVector.pop_back();
	currentSum -= root->data;
}

void BinTree::PrintVector(vector<BinTreeNode*> vec){

	//std::vector<BinTreeNode>::iterator iter = vec.begin();
	vector<BinTreeNode*>::iterator iter = vec.begin();

	while(iter != vec.end()){
		BinTreeNode* iterNode = *iter;
		cout<<iterNode->data;

		iter++;
	}
	
}

void BinTree::SearchToDoubleList(BinTreeNode* root){
	if(root == NULL){
		return;
	}
	//InOrderRecursion(root);
	BinTreeNode* lastVisit = NULL;
	SearchToListRecursion(root,&lastVisit);
	PrintTreeList(lastVisit);
}

void BinTree::SearchToListRecursion(BinTreeNode* root,BinTreeNode** lastVisit){

	if(root == NULL){
		return;
	}
	
	SearchToListRecursion(root->left,lastVisit);
	
	root->pre = *lastVisit;
	
	if(*lastVisit != NULL){
		(*lastVisit)->post = root;
	}

	*lastVisit = root;
	SearchToListRecursion(root->right,lastVisit);
}

void BinTree::SearchToListRecursion2(BinTreeNode* root,BinTreeNode* head,BinTreeNode* tail){
	if(root == NULL){
		return;
	}
	
	SearchToListRecursion2(root->left,head,tail);

	root->pre = head;
	if(head != NULL){
	}
}

void BinTree::PrintTreeList(BinTreeNode* root){
	if(root == NULL){
		return;
	}
	while(root != NULL){
		cout<<root->data<<'\t';
		root = root->pre;
	}
	while(root != NULL){
		cout<<root->data<<'\t';
		root = root->pre;
	}
	cout<<endl;
}

void BinTree::CommonNode(BinTreeNode* root,int first,int second){
	if(root == NULL || first == second){
		return;
	}
	BinTreeNode* commonNode = CommonNodeRecursion(root,first,second);
	cout<<commonNode->data<<endl;
}

BinTreeNode* BinTree::CommonNodeRecursion(BinTreeNode* root,int first,int second){
	if(root == NULL){
		return NULL;
	}

	if(root->data == first || root->data == second){
		return root;
	}

	BinTreeNode* leftNode = CommonNodeRecursion(root->left,first,second);
	BinTreeNode* rightNode = CommonNodeRecursion(root->right,first,second);

	if(leftNode != NULL && rightNode != NULL){
		return root;
	}
	if(leftNode == NULL && rightNode != NULL){
		return rightNode;
	}else if(leftNode != NULL && rightNode == NULL){
		return leftNode;
	}else{
		return NULL;
	}
}

void BinTree::CommonSearchNode(BinTreeNode* root,int first,int second){
	if(root == NULL){
		return;
	}
	int min,max;
	if(first>second){
		min = second;
		max = first;
	}else{
		min = first;
		max = second;
	}

	while(root != NULL){
		if(root->data<max&& root->data>min){
			cout<<root->data<<endl;
			return;
		}
		if(root->data<min && root->data<max){
			root = root->right;
		}else if(root->data>min && root->data>max){
			root = root->left;
		}else{
			return;
		}
	}
	return;
}

void BinTree::BreadthSearch(BinTreeNode* root){
	if(root == NULL){
		return;
	}
	queue<BinTreeNode*> treeQueue;
	treeQueue.push(root);
	while(!treeQueue.empty()){
		cout<<treeQueue.front()->data;
		
		if(treeQueue.front()->left != NULL){
			treeQueue.push(treeQueue.front()->left);
		}
		if(treeQueue.front()->right != NULL){
			treeQueue.push(treeQueue.front()->right);
		}
		treeQueue.pop();
	}
}